package org.lql.algo.codecrush.hot100.binaryTree;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-09-07 20:48
 * @description: 108. 将有序数组转换为二叉搜索树 <a href="https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class SortedArrayToBST {

	public TreeNode sortedArrayToBST(int[] nums) {
		return helperPreorder(nums, 0, nums.length - 1);
	}

	public TreeNode helperPreorder(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}
		// 总是选择中间位置左边的数字作为根节点
		int mid = (left + right) / 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = helperPreorder(nums, left, mid - 1);
		root.right = helperPreorder(nums, mid + 1, right);
		return root;
	}

	public TreeNode helperInorder(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}
		// 总是选择中间位置右边的数字作为根节点
		int mid = (left + right + 1) / 2;

		TreeNode root = new TreeNode(nums[mid]);
		root.left = helperInorder(nums, left, mid - 1);
		root.right = helperInorder(nums, mid + 1, right);
		return root;
	}
}
